package com.example;

/**
 * @Author loubobooo
 * @Description #19. 删除链表的倒数第N个节点
 * @Date 2022/3/8
 */
public class RemoveNthNodeFromEndOfList {

    /**
     * @return
     * @Author loubobooo
     * @Description 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
     * @Date 2022/3/8
     * @Param
     **/
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        // 避免头节点被删除，连接上dummyHead
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        // 删除是要找到待删除节点的前一个节点，因此P1和P2指向的节点不同
        // P1在前，P2在后，利用双指针P1,P2方法，遍历n次，让P1走到第n个节点
        ListNode p1 = head, p2 = dummyHead;
        for (int i = 0; i < n; i++) {
            p1 = p1.next;
        }
        // 利用p1继续往前走
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next = p2.next.next;

        return dummyHead.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        int[] arr2 = {4, 5, 1, 9};
        ListNode node2 = new ListNode(1);
        ListNode temp2 = node2;
        for (int i = 0; i < arr2.length; i++) {
            temp2.next = new ListNode(arr2[i]);
            temp2 = temp2.next;
        }
    }


}
